import random

BOARD_SIZE = 15

def generate_move(board, player):
    # 检查棋盘是否为空
    if is_empty_board(board):
        return random_move(board)
    empty_positions = [(i, j) for i in range(BOARD_SIZE) for j in range(BOARD_SIZE)
                          if board[i][j]==0]
    if not empty_positions:
        return None
    best_score = -float('inf')
    best_move = None
    for i, j in empty_positions:
        score = evaluate_position(board, i, j, player)
        # 同时考虑防守
        opponent = 2 if player == 1 else 1
        score += evaluate_position(board, i, j, opponent) * 0.8
        if score > best_score:
            best_score = score
            best_move = (i, j)
    return best_move

def is_empty_board(board):
    """检查棋盘是否为空"""
    for row in board:
        for cell in row:
            if cell != 0:
                return False
    return True

def random_move(board):
    """随机选择一个合法位置"""
    empty_positions = []
    for i in range(15):
        for j in range(15):
            if board[i][j] == 0:
                empty_positions.append((i, j))
    return random.choice(empty_positions)

# 落子分数评估
def evaluate_position(board, x, y, player):
    directions = [(1, 0), (0, 1), (1, 1), (1, -1)]
    score = 0

    for dx, dy in directions:
        count = 1
        block = 0

        # 正向检查
        tx, ty = x + dx, y + dy
        while 0 <= tx < BOARD_SIZE and 0 <= ty < BOARD_SIZE:
            if board[tx][ty] == player:
                count += 1
            elif board[tx][ty] == 0:
                break
            else:
                block += 1
                break
            tx += dx
            ty += dy

        # 反向检查
        tx, ty = x - dx, y - dy
        while 0 <= tx < BOARD_SIZE and 0 <= ty < BOARD_SIZE:
            if board[tx][ty] == player:
                count += 1
            elif board[tx][ty] == 0:
                break
            else:
                block += 1
                break
            tx -= dx
            ty -= dy

        # 评分
        if count >= 5:
            score += 100000
        elif count == 4:
            if block == 0:
                score += 10000
            elif block == 1:
                score += 1000
        elif count == 3:
            if block == 0:
                 score += 1000
            elif block == 1:
                score += 100
        elif count == 2:
            if block == 0:
                score += 100
            elif block == 1:
                score += 10

    return score